adaptive greedy
Revisiting the Approximation Bound for Stochastic Submodular Cover
Hellerstein, Lisa, Kletenik, Devorah
Deshpande et al. presented a k(ln R + 1) approximation bound for Stochastic Submodular Cover, where k is the state set size, R is the maximum utility of a single item, and the utility function is integer-valued. This bound is similar to the ln Q/(eta+1) bound given by Golovin and Krause, whose analysis was recently found to have an error. Here Q >= R is the goal utility and eta is the minimum gap between Q and any attainable utility Q' < Q. We revisit the proof of the k(ln R + 1) bound of Deshpande et al., fill in the details of the proof of a key lemma, and prove two bounds for real-valued utility functions: k(ln R_1 + 1) and (ln R_E + 1). Here R_1 equals the maximum ratio between the largest increase in utility attainable from a single item, and the smallest non-zero increase attainable from that same item (in the same state). The quantity R_E equals the maximum ratio between the largest expected increase in utility from a single item, and the smallest non-zero expected increase in utility from that same item. Our bounds apply only to the stochastic setting with independent states.
- North America > United States > New York > Kings County > New York City (0.04)
- North America > United States > Texas > Travis County > Austin (0.04)
- Europe > Denmark > Central Jutland > Aarhus (0.04)